package _11_整理题目._1_链表指针._删除节点;

import org.junit.Test;
import util.ListNode;


/**
 * 给出一个升序排序的链表，删除链表中的所有重复出现的元素，只保留原链表中只出现一次的元素。
 * 例如：
 * 给出的链表为 1  2 3 3 4 4 5, 返回 1 2 5.
 * 给出的链表为 1 1 2 3, 返回 2 3.
 * 
 * 由于可能删除第一个节点，所以设置伪结点，使用双指针 pre 和 cur 临时 nex 遍历删除重复元素
 * while() 由于要比较 cur 和 nex 节点的值是否相等，循环条件用 cur!=null && cur.next!=null
 *      判断 cur.val == cur.next.val
 *          取下 ListNode nex = cur.next;
 *          while(nex!=null && nex.val==cur.val)
 *              移动 nex = nex.next
 *          删除中间节点，即 pre.next = nex; cur = nex;
 *      否则 
 *          移动 pre 和 cur 到下一个节点
 * 遍历完后，即处理完毕，返回 fake.next
 * 
 */
public class _07_删除有序链表中重复出现的元素 {
    
    public ListNode deleteDuplicates (ListNode head) {
        ListNode fake = new ListNode(0);
        fake.next = head;
        
        ListNode pre = fake;
        ListNode cur = head;
        while (cur!=null && cur.next!=null) {
            if (cur.next.val == cur.val) {
                ListNode nex = cur.next;
                while (nex!=null && nex.val==cur.val) {
                    nex = nex.next;
                }
                pre.next = nex;
                cur = nex;
            } else {
                pre = pre.next;
                cur = cur.next;
            }
        }
        return fake.next;
    }
    
    @Test
    public void main() {
        Integer[] array = {1, 1, 3, 5, 5, 7, 9};
        ListNode head = ListNode.getListFromArray(array);
        ListNode.printList(head);
        ListNode result = deleteDuplicates(head);
        ListNode.printList(result);
    }
    
}
